package 题目集.拓扑排序;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 思路1：dfs+记忆化搜索+反向边
 * 思路2：拓扑排序
 * https://leetcode.cn/problems/parallel-courses-iii/description/
 */
public class ch03_并行课程III {
    List<Integer>[] graph;

    public int minimumTime(int n, int[][] relations, int[] time) {
        graph = new List[n];
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : relations) {
            graph[r[0] - 1].add(r[1] - 1);
            inDegree[r[1] - 1]++;
        }
        int[] queue = new int[n + 1];
        int head = 0, tail = 0;
        int[] lastTimes = new int[n];
        for (int i = 0; i < inDegree.length; i++) {
            lastTimes[i] = time[i];
            if (inDegree[i] == 0) {
                queue[tail++] = i;
            }
        }
        int res=0;
        while (head < tail) {
            int cur = queue[head++];
            res = Math.max(res, lastTimes[cur]);    //结算当前点
            for (int to : graph[cur]) {
                inDegree[to]--;
                lastTimes[to] = Math.max(lastTimes[to], lastTimes[cur] + time[to]);
                if (inDegree[to] == 0) {
                    queue[tail++] = to;
                }
            }
        }
        return res;
    }

    @Test
    public void test() {
        System.out.println(minimumTime(5, new int[][]{{2, 1}, {3, 1}, {4, 1}, {1, 5}}, new int[]{3, 2, 4, 1, 5}));
    }
}
